/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package npuzzle;

import algoritmo.Node;
import java.awt.Point;
import java.util.*;

/**
 * Representa una configuración específica del juego del n-puzzle y contiene la
 * lógica para realizar movimientos
 */
public class PuzzleNode extends Node {

    public static final int UP = 0;
    public static final int DOWN = 1;
    public static final int LEFT = 2;
    public static final int RIGHT = 3;
    /*
     * Profundidad del nodo (cuantas veces ha sido expandido)
     */
    private int depth;
    /*
     * Representa los cuadros del juego. La casilla vacía se representa con un 0
     */
    private int[][] estado;
    /*
     * Tamaño del tablero en casillas por lado
     */
    public int n;
    /*
     * El número del cuadro que fue movido para alcanzar la configuraión actual
     */
    private int lastMoved;
    /*
     * La dirección en la cual se movió el último cuadro movido
     */
    private int lastDir;

    /* Construye un nodo con la configuracion especificada
     * @param n casillas por lado
     */
    public PuzzleNode(int[][] arr, int n) {

        this.n = n;
        this.estado = arr;
    }
    
    /*
     * Regresa un nodo con una configuración ordenada normal, del tamaño especificado.
     * @param n el tamaño del tablero en casillas por lado
     * @return una instancia de nodo con orden normal
     */
    public static PuzzleNode createOrdered(int n) {
        int[][] arr = new int[n][n];
        int nsqr = n * n;
        int num = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (num == nsqr) {
                    arr[i][j] = 0;
                } else {
                    arr[i][j] = num;
                }
                num++;
            }
        }
        PuzzleNode pn = new PuzzleNode(arr, n);
        return pn;
    }
    
    /*
     * Regresa un nodo con una configuración ordenada en reversa, del tamaño especificado.
     * @param n el tamaño del tablero en casillas por lado
     * @return la instancia ordenada en reversa
     */
    public static PuzzleNode createReversed(int n) {
        int[][] arr = new int[n][n];
        int nsqr = n * n;
        int num = nsqr;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (num == nsqr) {
                    arr[i][j] = 0;
                } else {
                    arr[i][j] = num;
                }
                num--;

            }
        }
        PuzzleNode pn = new PuzzleNode(arr, n);
        return pn;
    }

    /*
     * Regresa un nodo con una configuración aleatoria, del tamaño especificado.
     * @param n el tamaño del tablero en casillas por lado
     * @return una instancia aleatoria
     */
    public static PuzzleNode createRandom(int n) {
        int nsq = n * n;
        Integer[] arr = new Integer[nsq];
        for (int i = 0; i < nsq; i++) {
            arr[i] = i;
        }
        Collections.shuffle(Arrays.asList(arr));
        int arr2[][] = new int[n][n];
        int i, j, k;
        for (i = 0, j = 0, k = 0; i < nsq; i++) {
            arr2[j][k] = arr[i];
            k++;
            if (k == n) {
                k = 0;
                j++;
            }
        }
        PuzzleNode pn = new PuzzleNode(arr2, n);
        return pn;
    }

    /*
     * Obtiene un nuevo nodo que tiene una configuración igual a la configuración 
     * de este nodo tras aplicarle n operaciones aleatorias
     * @param n el número de operaciones a aplicar
     */
    public PuzzleNode scramble(int n) {
        PuzzleNode pn = new PuzzleNode(getEstado(), this.n);
        PuzzleNode t;
        for (int i = 0; i < n; i++) {
            do {
                int rand = new Random().nextInt(4);
                t = pn.move(rand);
            } while (t == null);
            pn = t;
        }
        return pn;
    }

    /* Obtiene hasta 4 nodos hijos que resultan de aplicar las operaciones 
     * de movimiento posibles
     * @return la lista de nodos hijos
     */
    @Override
    public List<PuzzleNode> expand() {
        List<PuzzleNode> children = new ArrayList<>();
        PuzzleNode child;
        if ((child = move(UP)) != null) {
            child.setPrev(this);
            child.setDepth(this.getDepth() + 1);
            children.add(child);
        }
        if ((child = move(DOWN)) != null) {
            child.setPrev(this);
            child.setDepth(this.getDepth() + 1);
            children.add(child);
        }
        if ((child = move(LEFT)) != null) {
            child.setPrev(this);
            child.setDepth(this.getDepth() + 1);
            children.add(child);
        }
        if ((child = move(RIGHT)) != null) {
            child.setPrev(this);
            child.setDepth(this.getDepth() + 1);
            children.add(child);
        }
        return children;
    }
    /*
     * Aplica una operación de movimiento, que puede ser:<br />
     * <ul>
     * <li><b>UP</b> Mueve el cuadro que esté libre para moverse hacia arriba. 
     * No es posible si la casilla vacía está en la última fila.</li>
     * <li><b>DOWN</b> Mueve el cuadro que esté libre para moverse hacia abajo. 
     * No es posible si la casilla vacía está en la primera fila.</li>
     * <li><b>LEFT</b> Mueve el cuadro que esté libre para moverse a la izquierda. 
     * No es posible si la casilla vacía está en la última columna.</li>
     * <li><b>RIGHT</b> Mueve el cuadro que esté libre para moverse a la derecha. 
     * No es posible si la casilla vacía está en la primera columna.</li>
     * </ul>
     * 
     * @param operation la operación de movimiento
     * @return el nodo con la configuración resultante o null si la operación
     * especificada no se puede llevar a cabo o se especificó una operación
     * inexistente
     */

    public PuzzleNode move(int operation) {
        PuzzleNode node = null;
        int[][] copy = getEstado();
        Point empty = getEmpty();
        int i = empty.x;
        int j = empty.y;
        int moved = 0;
        switch (operation) {
            case UP:
                if (i != n - 1) {
                    copy[i][j] = estado[i + 1][j];
                    copy[i + 1][j] = 0;
                    moved = copy[i][j];
                }
                break;
            case DOWN:
                if (i != 0) {
                    copy[i][j] = estado[i - 1][j];
                    copy[i - 1][j] = 0;
                    moved = copy[i][j];
                }
                break;
            case LEFT:
                if (j != n - 1) {
                    copy[i][j] = estado[i][j + 1];
                    copy[i][j + 1] = 0;
                    moved = copy[i][j];
                }
                break;
            case RIGHT:
                if (j != 0) {
                    copy[i][j] = estado[i][j - 1];
                    copy[i][j - 1] = 0;
                    moved = copy[i][j];
                }
                break;
        }
        if (moved != 0) {
            node = new PuzzleNode(copy, this.n);
            node.setLastMoved(moved);
            node.setLastDir(operation);
        }
        return node;
    }

    /* Busca la posición de la casilla vacía en esta configuración
     * @return un Point con la posicion i,j
     */
    public Point getEmpty() {
        Point pos = null;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (estado[i][j] == 0) {
                    pos = new Point(i, j);
                }
            }
        }
        return pos;
    }

    public int getCasilla(int i, int j) {
        return estado[i][j];
    }

    /* 
     * Regresa el número del último cuadro movido, que es el cuadro que fue movido
     * para que este nodo alcanzara su configuración actual
     * @return el número del cuadro, o cero si es el primer nodo
     */
    public int getLastMoved() {
        return lastMoved;
    }

    private void setLastMoved(int lastMoved) {
        this.lastMoved = lastMoved;
    }

    /* Regresa la dirección (PuzzleNode.UP, PuzzleNode.DOWN, PuzzleNode.LEFT
     * o PuzzleNode.RIGHT) en la cual se movió el cuadro que se movió para que el 
     * juego alcanzara la configuración actual
     * @return entero representando la dirección
     */
    public int getLastDir() {
        return lastDir;
    }

    private void setLastDir(int lastDir) {
        this.lastDir = lastDir;
    }

    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }

    /*Regresa una copia del estado del nodo
     * @return una copia del arreglo bdimensional con la que se representa el
     * estado de este nodo
     */
    public int[][] getEstado() {
        int[][] copy = new int[n][n];
        for (int i = 0; i < n; i++) {
            System.arraycopy(estado[i], 0, copy[i], 0, n);
        }
        return copy;
    }

    public void setEstado(int[][] estado) {
        this.estado = estado;
    }

    public int manhattan(PuzzleNode n2) {
        int distancia = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int casilla = getCasilla(i, j);
                if (casilla != 0 && casilla != n2.getCasilla(i, j)) {
                    Point pos2 = n2.whereIs(casilla);
                    distancia += manhattan(i, j, pos2.x, pos2.y);
                }
            }
        }
        return distancia;
    }

    private Point whereIs(int num) {
        Point pos = null;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (getCasilla(i, j) == num) {
                    pos = new Point(i, j);
                }
            }
        }
        return pos;
    }

    public static int manhattan(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    /*
     * Regresa la representación en cadena de la configuración del juego,
     * en forma de tabla, con un * en la casilla vacía.
     * @return la representación en cadena
     */
    @Override
    public String toString() {
        String s = "";
        for (int i[] : estado) {
            for (int j : i) {
                if (j == 0) {
                    s += String.format("  * ");
                } else {
                    s += String.format(" %2d ", j);
                }
            }
            s += "\n\r";
        }
        return s;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final PuzzleNode other = (PuzzleNode) obj;
        if (!Arrays.deepEquals(this.estado, other.estado)) {
            return false;
        }
        return true;
    }

    @Override
    public int hashCode() {
        int hash = 3;
        hash = 13 * hash + Arrays.deepHashCode(this.estado);
        hash = 13 * hash + this.n;
        return hash;
    }

    @Override
    public int getDepth() {
        return depth;
    }

    private void setDepth(int depth) {
        this.depth = depth;
    }
}
